#include <iostream>
using namespace std;

template <typename T>
class List
{
private:
    struct Node
    {
	T data;
	Node* prev;
	Node* next;
	Node(const T& d = T(), Node* p = NULL, Node* n = NULL)
	    :data(d), prev(p), next(n){};
    };
    
public:
    class const_iterator
    {
    protected:
	Node* current;
	T& retrieve() const
	{
	    return current->data;
	};
	const_iterator(Node* p):current(p){};
	friend class List<T>;//允许list内函数调用这个class的参数，当然派生也是
    public:
	const_iterator():current(NULL){};
	const T& operator * () const
	{
	    return retrieve();
	}
	const_iterator& operator ++ ()
	{
	    current = current->next;
	}
	const_iterator& operator -- ()//书上缺少--，下同
	{
	    current = current->prev;
	}
	const_iterator operator ++ (int)//区别前后++，给前缀空参数，后缀匿名int参数
	{
	    const_iterator old = *this;
	    ++(*this);
	    return old;
	}
	const_iterator operator -- (int)
	{
	    const_iterator old = *this;
	    --(*this);
	    return old;
	}
	bool operator == (const const_iterator& rhs) const
	{
	    return current == rhs.current;
	}
	bool operator != (const const_iterator& rhs) const
	{
	    return !(*this == rhs);
	}
    };
	
	    
    class iterator:public const_iterator
    {
    protected:
        iterator(Node* p):const_iterator(p){};
	friend class List<T>;
    public:
	iterator(){}
	T& operator * ()
	{
	    return const_iterator::retrieve();//书上缺少const_iterator，则无法调用基类函数
	}
	const T& operator * () const
        {
	    return const_iterator::operator*();
	}
	iterator& operator ++ ()
	{
	    this->current = this->current->next;//书上缺少this，则无法使用基类参数
	    return *this;
	}
	iterator& operator -- ()//书上缺少--，下同
	{
	    this->current = this->current->prev;
	    return *this;
	}
	iterator operator ++ (int)//为何不加&？？
	{
	    iterator old = *this;
	    ++(*this);
	    return old;
	}
	iterator operator -- (int)
	{
	    iterator old = *this;
	    --(*this);
	    return old;
	}
    };

    
private:
    int theSize;
    Node* head;
    Node* tail;

public:
    List()
    {
	init();
    }
    ~List()
    {
	clear();
	delete head;
	delete tail;
    }
    const List& operator = (const List& rhs)
    {
	if (this == &rhs)
	    return *this;
	clear();
	for(const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
	    push_back(*itr);
	return *this;
    }
    iterator begin()
    {
	return iterator(head->next);
    }
    const iterator begin() const
    {
	return const_iterator(head->next);
    }
    iterator end()
    {
	return iterator(tail);
    }
    const iterator end() const
    {
	return const_iterator(tail);
    }
    int size() const
    {
        return theSize;
    }
    bool empty() const
    {
        return size() == 0;
    }
    void clear()
    {
	while (!empty())
	    pop_front();
    }
    
    T& front()
    {
        return *begin();
    }
    const T& front() const
    {
	return *begin();
    }
    T& back()
    {
	return *--end();
    }
    const T& back() const
    {
	return *--end();
    }
    void push_front(const T& _x)
    {
	insert(begin(), _x);
    }
    void push_back(const T& _x)
    {
	insert(end(), _x);
    }
    void pop_front()
    {
	erase(begin());
    };
    void pop_back()
    {
	erase(--end());
    }
    
    iterator insert(iterator itr, const T& _x)
    {
	Node *p = itr.current;
	theSize++;
	return iterator(p->prev = p->prev->next = new Node(_x, p->prev, p));
    }
    iterator erase(iterator itr)
    {
	Node *p = itr.current;
	iterator retVal(p->next);
	p->prev->next = p->next;
	p->next->prev = p->prev;
	delete p;
	theSize--;
	return retVal;
    }
    iterator earse(iterator start, iterator end)
    {
	for (iterator itr = start; itr != end; )//书上莫明用from to，当为start end
	    itr = erase(itr);
	return end;
    }

    void init()
    {
	theSize = 0;
	head = new Node;
	tail = new Node;
	head->next = tail;
	tail->prev = head;
    }
};


	    
	    
    
    
    
	
    
